A fully homomorphic encryption scheme (FHE) is an encryption scheme that allows evaluation of arbitrary functions on encrypted data. Since Gentry's mathematical breakthrough constructing the first plausible FHE scheme, there has been rapid development in the theory and implementation of homomorphic encryption (HE) schemes. HE schemes can now be based on a variety of cryptographic assumptions, such as approximate greatest common divisors, learning with errors (LWE), and Ring-LWE (RLWE).
Known implementations RLWE-based FHE schemes have drawbacks, such as the need to maintain a so-called “modulus chain” which increases the size of prime numbers and consequently increases the ring dimension for a given security level. They also often need to perform processing intensive modulus and key switching operations.
Searching an encrypted database is generally known, but often has drawbacks, such as the need for a special key to aid the server in performing a search request. In some cases, partial information about the data access pattern is leaked. In some cases, the same server requests would generate the same tags.
In general, known fully homomorphic encryption systems require a large amount of storage space and a high degree of processing power. As such, known systems are cumbersome and not widely used. Other drawbacks of conventional systems are known to those skilled in the art.